//顺序表动态内存分配
#include <stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXSIZE 100
typedef int ElemType;

typedef struct
{
    ElemType *data;
    int length;
}SeqList;

//动态内存分配初始化顺序表
SeqList* InitList()
{
    SeqList *L = (SeqList*)malloc(sizeof(SeqList));
    L->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    L->length = 0;
    printf("初始化成功\n");
    return L;
}

//在尾部添加元素
void AddList(SeqList *L, ElemType e)
{
    if (L->length >= MAXSIZE)
    {
        printf("顺序表已满\n");
        return;
    }
    L->data[L->length] = e;
    L->length++;
}

//插入元素
void InsertList(SeqList *L, int i, ElemType e)
{
    if (i < 1 || i > L->length + 1)
    {
        printf("插入位置错误\n");
        return;
    }
    
    if (L->length >= MAXSIZE)
    {
        printf("顺序表已满\n");
        return;
    }

    for (int j = L->length; j >= i;j--)
    {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    printf("插入成功\n");

}

//删除元素（后面的把前面的覆盖）
void DeleteList(SeqList *L, int i, ElemType *e)
{
    if(L->length == 0)
    {
        printf("顺序表为空\n");
        return;
    }
    if (i < 1 || i > L->length)
    {
        printf("删除位置错误\n");
        return;
    }

    *e = L->data[i-1];//存放被删除的数据
    for (int j = i; j < L->length; j++) //实际上最后一个位置的元素没有往前挪，不用管，因为最后会length--，下次添加的时候会覆盖
    {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    printf("删除成功\n");

}

//查找数据位置
int LocateElem(SeqList *L, ElemType e)
{
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] == e)
        {
            return i+1;
        }
    }
    return 0;
}

//遍历顺序表
void TraverseList(SeqList *L)
{
    for (int i = 0; i < L->length; i++)
    {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

//输出元素个数
int ListLength(SeqList *L)
{
    return L->length;
}

//清空线性表
void ClearList(SeqList *L)
{
    L->length = 0;
}


int main()
{
    //声明一个线性表并初始化
    SeqList* list = InitList();
    printf("目前占用长度：%d\n",list->length);
    printf("目前占用内存%zu字节\n",sizeof(list->data));

    //尾部添加元素
    printf("尾部添加元素：\n");
    AddList(list,1);
    AddList(list,2);
    AddList(list,3);
    AddList(list,4);
    printf("当前线性表为：\n");
    TraverseList(list);

    //插入元素
    printf("插入元素：\n");
    InsertList(list,2,5);
    printf("当前线性表为：\n");
    TraverseList(list);

    //删除元素
    printf("删除元素：\n");
    ElemType delData;
    DeleteList(list,2,&delData);
    printf("删除的元素为：%d\n",delData);
    printf("当前线性表为：\n");
    TraverseList(list);

    //查找元素
    printf("查找元素：\n");
    ElemType e;
    printf("请输入要查找的元素：\n");
    scanf("%d",&e);
    printf("元素%d的位置为：%d\n",e,LocateElem(list,e));

    //输出元素个数
    printf("当前线性表元素个数为：%d\n",ListLength(list));

    //清空线性表
    ClearList(list);
    printf("清空线性表后，线性表为：\n");
    TraverseList(list);

    return 0;
}
